import java.util.HashMap;
import java.util.Iterator;

/**
 * Optimal optimizer, slow version that
 * computes results for all boxes, even those with no bits. 
 * @author Ed Hong
 *
 */
public class SlowOptimalOptimizer extends AbstractOptimalOptimizer {

        public static final BitCounts ZEROBC = new BitCounts(0,0);
        
        HashMap<ContextCharacteristicsBox, BitCounts> allCounts; // store of bitcounts for each set.
 
        // recursive dynprog solution. 
            static int solvecount = 0;        
    protected solutionInfo solve(ContextCharacteristicsBox cb, double threshold) {
            if (DEBUG && ((solvecount++) % 100000 == 0)) {
             System.out.println(cb + " numsol:" + allSol.size() + 
				 " solvecount:" + solvecount);
            }
            solutionInfo si;
            
            si = allSol.get(cb);
            if (si != null) 
                return si;
            else if (cb.isSingletonBox()) {
                BitCounts bc;
                bc = contextData.get(cb.getlower());
                if (bc == null) { 
                    si = new solutionInfo(null, 0);
                    bc = ZEROBC;
                }
                else 
                    si = new solutionInfo(null, 
                        Cost.adaptiveCostEstimate(bc));
                allSol.put(cb,si);
                allCounts.put(cb,bc);
                return si;
            }
            else  {
                // for each split criteria possible in cb
                // recursively solve
                // store overall min in allSol
                // return min. 
                
		Iterator<SplitCriteria> iter = cb.getSplitIterator();
                solutionInfo best;
                solutionInfo sol1, sol2;
                best = new solutionInfo(null, Double.POSITIVE_INFINITY);
                int numcriteria = 0;
                ContextCharacteristicsBox[] boxes;
                boxes = new ContextCharacteristicsBox[2];
                boxes[0] = boxes[1] = null;
		while (iter.hasNext()) {
			SplitCriteria criteria = iter.next();
                        numcriteria++;
                        boxes = cb.split(criteria);
//                        System.out.println("Box0: " + boxes[0]);
//                        System.out.println("Box1: " + boxes[1]);
                        sol1 = solve(boxes[0],threshold);
                        sol2 = solve(boxes[1],threshold);
                        double combined = sol1.cost + sol2.cost; 
                        if (combined < best.cost) {
                            best.cost = combined;
                            best.splitc = criteria;
                        }
                }
                if (numcriteria == 0) {
                    throw new IllegalArgumentException("solve:no valid split found");
                }
                // add split cost here                      
                best.cost += Cost.splitCost(numcriteria);
                
                // compare best so far with no splitting. 
                BitCounts newbc;
                newbc =new BitCounts(0,0);
                newbc.add(allCounts.get(boxes[0]));
                newbc.add(allCounts.get(boxes[1]));
                double newcost = Cost.adaptiveCostEstimate(newbc);
                if (newcost <= best.cost) {
                    best.cost = newcost;
                    best.splitc = null;
                }
                  
                allSol.put(cb,best);
                allCounts.put(cb,newbc);
//                System.out.print(best + " " + newbc + " " );
                return best;
            }   
        }
        
	
	public SlowOptimalOptimizer(String ccdFile) {
		super(ccdFile);
                allCounts = new HashMap<ContextCharacteristicsBox, BitCounts>( );
	}
	

        protected void buildOptimalTree(ContextCharacteristicsBox cb, 
                                ContextTreeNode currnode) {
                solutionInfo si = allSol.get(cb);        
                if (si.splitc != null) {
                    currnode.split(si.splitc);
                    ContextCharacteristicsBox[] boxes = cb.split(si.splitc); 
                    buildOptimalTree(boxes[0],currnode.getLeftChild());              
                    buildOptimalTree(boxes[1],currnode.getRightChild());                                  
                }
        }
        
}
